package org.dlx.common;

import java.sql.ResultSet;

//二叉排序树 左小右大
public class BinOrderTree
{
    public static void main(String[] args){
        BinOrderTree bot = new BinOrderTree();
        bot.addNode(62);
        bot.addNode(88);
        bot.addNode(58);
        bot.addNode(47);
        bot.addNode(62);
        bot.addNode(35);
        bot.addNode(73);
        bot.addNode(51);
        bot.addNode(99);
        bot.addNode(37);
        bot.addNode(93);
        bot.midOrder();
        SearchResult sr;
        sr = bot.remove(bot.find(99));
        sr = bot.remove(bot.find(35));
        sr = bot.remove(bot.find(37));
        sr = bot.remove(bot.find(62));
        bot.midOrder();
    }

    private Node root;//根节点默认为空

    public void addNode(int value) {
        SearchResult sr = search(value);
        if(sr.Target != null)
            return;//已经存在了

        if(sr.Hot == null) {
            root = new Node(value);
        }else{
            Node node = new Node(value);
            if(value < sr.Hot.getValue()){
                sr.Hot.setLeft(node);
            }else{
                sr.Hot.setRight(node);
            }
            node.setParent(sr.Hot);
        }
    }
    //左小右大
    private void addNode(Node value, Node parent){
        if(value.getValue() < parent.getValue()) {
            //选择左子树
            if(parent.getLeft() == null){
                parent.setLeft(value);
                value.setParent(parent);
            } else{
                //左子树有了 递归
                addNode(value, parent.getLeft());
            }
        }else if(value.getValue() > parent.getValue()){
            if(parent.getRight() == null) {
                parent.setRight(value);
                value.setParent(parent);
            } else{
                addNode(value, parent.getRight());
            }
        }
    }

    public int min(){
        if(root == null){
            throw new RuntimeException("内容为空");
        }
        Node current = root;
        while(current.getLeft() != null) {
            current = current.getLeft();
        }
        return current.getValue();
    }

    public int max(){
        if(root == null){
            throw new RuntimeException("内容为空");
        }
        Node current = root;
        while(current.getRight() != null){
            current = current.getRight();
        }
        return current.getValue();
    }
    //搜索 如果没找到则hot代表可以插入的节点
    // (null, null), (h, null), (null, t), (h,t)
    public SearchResult search(int value){
        if(root == null)
            return new SearchResult(null, null);
        Node hot = null;
        Node current = root;
        while(current != null){
            if(current.getValue() == value){
                return new SearchResult(hot, current);
            }
            hot = current;
            if(current.getValue() < value) {
                current = current.getRight();
            } else{
                current = current.getLeft();
            }
        }
        return new SearchResult(hot,null);
    }
    //删除是基于查找的
    public Node find(int value){
        //查找的时候 如果树里有多个相同的值 返回第一个
        //二叉排序 感觉很少会处理值相同的情况
        Node current = root;
        while(current != null){
            if(current.getValue() == value) {
                break;
            }
            if(current.getValue() < value){ //value大 那么只可能再右子树上
                current = current.getRight();
            } else{
                current = current.getLeft();
            }
        }
        return current;
    }
    //被删除的节点和节点删除前的父
    public SearchResult remove(Node n) {
        if(n == null)
            return null;
        //分情况
        if(n.getLeft() != null && n.getRight() != null) {
            //在两个节点都存在的情况下 查找最小右子树
            Node current = n.getRight();
            while(current.getLeft() != null)
                current = current.getLeft();
            //交换2个节点的值
            int tmp = n.getValue();
            n.setValue(current.getValue());
            current.setValue(tmp);
            return remove(current);
        }else{
            //这里其实是分为叶子节点和只有1个子节点的情况
            //但叶子节点可以考虑 是只有1个子节点的特殊情况
            //这里都是子节点和自己的父节点相连
            //child 从父上摘除
            boolean left = n.getLeft() != null;
            Node child = null;
            if(left) {
                child = n.getLeft();
                n.setLeft(null);
            }else{
                child = n.getRight();
                n.setRight(null);
            }
            if(child != null)
                child.setParent(null);

            Node grad = null;
            if(n == root)
                root = child;
            else
            {
                //父从祖父摘除
                grad = n.getParent();
                n.setParent(null);
                //子添加到祖父上
                boolean leftGrad = grad.getLeft() == n;
                if(leftGrad)
                    grad.setLeft(child);
                else
                    grad.setRight(child);
                if(child != null)
                    child.setParent(grad);
            }
            return new SearchResult(grad, n);
        }
    }

    //遍历的3种方法 前中后
    //前序遍历
    public void preOrder(){
        System.out.println("前序遍历");
        preOrder(root);
        System.out.println("end");
    }

    void preOrder(Node node){
        if(node == null){
            return;
        }
        System.out.println(node.getValue());
        preOrder(node.getLeft());
        preOrder(node.getRight());
    }
    //中序遍历
    public void midOrder(){
        System.out.println("中序遍历");
        midOrder(root);
        System.out.println("end");
    }

    private void midOrder(Node node){
        if(node == null){
            return;
        }
        midOrder(node.getLeft());
        System.out.println(node.getValue());
        midOrder(node.getRight());
    }
    //后序遍历
    public void postOrder(){
        System.out.println("中序遍历");
        postOrder(root);
        System.out.println("end");
    }

    private void postOrder(Node node){
        if(node == null){
            return;
        }
        postOrder(node.getLeft());
        postOrder(node.getRight());
        System.out.println(node.getValue());
    }

    public static class SearchResult{
        public Node Hot;
        public Node Target;

        public SearchResult(Node h, Node t){
            Hot = h;
            Target = t;
        }
    }

    public static class Node{
        int value;
        Node left;
        Node right;
        Node parent;

        public Node(int v){
            value = v;
        }

        public Node getParent()
        {
            return parent;
        }

        public void setParent(Node parent)
        {
            this.parent = parent;
        }

        public int getValue()
        {
            return value;
        }

        public void setValue(int value)
        {
            this.value = value;
        }

        public Node getLeft()
        {
            return left;
        }

        public void setLeft(Node left)
        {
            this.left = left;
        }

        public Node getRight()
        {
            return right;
        }

        public void setRight(Node right)
        {
            this.right = right;
        }
    }


}
